package LeetCode;


public class Code21_mergeTwoLists {
//    21. 合并两个有序链表
//将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
//
//    输入：l1 = [1,2,4], l2 = [1,3,4]
//    输出：[1,1,2,3,4,4]
//    示例 2：
//
//    输入：l1 = [], l2 = []
//    输出：[]
//    示例 3：
//
//    输入：l1 = [], l2 = [0]
//    输出：[0]
    class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }

    /**
     * 合并两个有序链表
     * 将两个有序链表合并为一个新的有序链表并返回新链表的头节点
     *
     * @param a 第一个有序链表的头节点
     * @param b 第二个有序链表的头节点
     * @return 合并后的有序链表的头节点
     */
    public ListNode mergeTwoLists(ListNode a, ListNode b) {
        // 如果其中一个链表为空，则直接返回另一个链表
        if (a == null || b == null){
            return a == null ? b : a;
        }

        // 创建一个虚拟头节点，简化链表操作
        ListNode dummy = new ListNode(0);

        // 根据两个链表头节点的值，确定合并后的链表的第一个节点
        dummy.next = a.val <= b.val ? a : b;

        // 初始化指针p，用于遍历和构建合并后的链表
        ListNode p = dummy;

        // 遍历两个链表，直到至少有一个链表遍历到末尾
        while (a.next != null && b.next != null){
            // 比较当前节点的值，将较小值的节点添加到合并后的链表
            if (a.val <= b.val){
                p.next = a;
                a = a.next;
            } else {
                p.next = b;
                b = b.next;
            }
            p = p.next;
        }

        // 将剩余未遍历完的链表直接连接到合并后链表的末尾
        p.next = a.next != null ? a : b;

        // 返回合并后的链表的头节点
        return dummy.next;
    }

}
